package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.List;

public class PascalTriangle {

	public static void main(String[] args) {
		PascalTriangle ins = new PascalTriangle();
		ins.generate(3);
	}
	
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		if (numRows <= 0) return res;
		
		List<Integer> cur = new ArrayList<Integer>();
		cur.add(1);
		res.add(cur);
		
		for (int i = 1; i < numRows; i++) {
			List<Integer> row = new ArrayList<Integer>();
			row.add(1);
			
			int j = 0;
			while (j < i) {
				int val = res.get(i-1).get(j);
				if (j + 1 < i) {
					val += res.get(i-1).get(j+1);
				}
				row.add(val);
				j++;
			}
			res.add(row);
		}
		return res;
	}
	
	
	// An old recursive solution
	public ArrayList<ArrayList<Integer>> generateRecursion(int numRows) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        
        if (numRows <= 0) return res;
        
        ArrayList<Integer> cur = new ArrayList<Integer>();
        cur.add(1);
        generateHelper(res, cur, 1, numRows);
        
        return res;
    }
    
    private void generateHelper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int curRow, int numRows) {
        res.add(cur);
        
        if (curRow == numRows) return;
        
        ArrayList<Integer> next = new ArrayList<Integer>();
        next.add(0, cur.get(0));
        for (int i = 1; i < cur.size(); ++i) {
            next.add(cur.get(i-1) + cur.get(i));
        }
        next.add(cur.get(cur.size() - 1));
        generateHelper(res, next, curRow + 1, numRows);
    }
    

}
